/*
 * @lc app=leetcode.cn id=25 lang=golang
 *
 * [25] K 个一组翻转链表
 */

// 3. stack 这个更好理解
// 递归的本质就是栈，任何递归都可以使用栈来实现
// @lc code=start
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
	stack := make([]*ListNode, 0)

	dummyHead := &ListNode{0, nil}
	pre := dummyHead

	for head != nil {
		i := 0
		temp := head
		for ; i < k && temp != nil; i++ {
			stack = append(stack, temp)
			temp = temp.Next
		}
		if i != k {
			pre.Next = head
			break
		}

		for i := 0; i < len(stack); { // 无需 i++
			pre.Next = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			pre = pre.Next
		}
		pre.Next = nil // 需要断掉，否则当（i==k && temp==nil）时 会成环
		head = temp
	}

	return dummyHead.Next
}

// @lc code=end

// 2. 递归，这个好理解一点
// @lc code=start
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
	temp := &ListNode{0, head}
	for i := 0; i < k && temp != nil; i++ {
		temp = temp.Next
	}

	if temp == nil {
		return head
	}

	next := temp.Next
	temp.Next = nil

	ans := reverseList(head)
	head.Next = reverseKGroup(next, k)

	return ans
}

// 从206 翻转链表拷贝过来的
func reverseList(head *ListNode) *ListNode {
	var pre *ListNode
	for head != nil {
		next := head.Next
		head.Next = pre

		pre = head
		head = next
	}
	return pre
}

// @lc code=end

// 1. 迭代，这个不大好理解
// @lc code=start
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
	var dummyHead = &ListNode{0, head}

	pre := dummyHead
	temp := dummyHead
	for temp != nil {
		i := 0
		for ; i < k && temp != nil; i++ {
			temp = temp.Next
		}

		if i == k && temp != nil {
			next := temp.Next
			temp.Next = nil

			pre.Next = reverseList(head)
			pre = head
			head = next
			temp = &ListNode{0, head}
		}
	}

	pre.Next = head
	return dummyHead.Next
}

// 从206 翻转链表拷贝过来的
func reverseList(head *ListNode) *ListNode {
	var pre *ListNode
	for head != nil {
		next := head.Next
		head.Next = pre

		pre = head
		head = next
	}
	return pre
}

// @lc code=end

